import ILinkedList from "../types/ILinkedList";

// 定义一个泛型类Node，用于存储数据
class Node<T> {
  // 定义一个指向下一个节点的指针，初始值为null
  next: Node<T> | null = null;
  // 构造函数，接收一个泛型参数value，用于存储数据
  constructor(public value: T) {}
}

class LinkedList<T> implements ILinkedList<T> {
  // 定义链表的头节点和链表长度
  private head: Node<T> | null = null;
  private size: number = 0;

  // 根据位置获取节点
  private _getNode(position: number): Node<T> | null {
    let index = 0;
    let current = this.head;
    while (index++ < position && current) {
      current = current.next;
    }
    return current;
  }
  // 在链表末尾添加节点
  append(value: T): void {
    const newNode = new Node<T>(value);
    if (!this.head) {
      this.head = newNode;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = newNode;
    }
    this.size++;
  }

  // 在指定位置插入节点
  insert(value: T, position: number): boolean {
    if (position < 0 || position > this.size) return false;
    const newNode = new Node<T>(value);
    if (position === 0) {
      newNode.next = this.head;
      this.head = newNode;
    } else {
      // let current = this.head;
      // let previous: Node<T> | null = null;
      // let index = 0;
      // while (index++ < position && current) {
      //   previous = current;
      //   current = current.next;
      // }
      // // index === position
      // newNode.next = current;
      // previous!.next = newNode;
      // pervious是当前节点, next是下一个节点
      /**
       * {
       *   value: 'a',
       *   next: {
       *     value: 'b',
       *     next: {
       *       value: 'c',
             }
            }
       * }
      */
      const previous = this._getNode(position - 1);
      newNode.next = previous!.next;
      previous!.next = newNode;
    }
    this.size++;
    return true;
  }
  // 根据位置获取节点值
  get(position: number): T | null {
    if (position < 0 || position >= this.size) return null;
    return this._getNode(position)?.value ?? null;
  }

  // 根据位置删除节点
  removeAt(position: number): T | null {
    if (position < 0 || position >= this.size) return null;
    let current = this.head;
    if (position === 0) {
      this.head = current?.next || null;
    } else {
      // 重构代码
      const previousNode = this._getNode(position - 1);

      // 需要给current重新赋值
      current = previousNode!.next;

      // 找到需要的节点
      previousNode!.next = previousNode?.next?.next ?? null;
    }
    this.size--;
    return current?.value ?? null;
  }
  // 遍历链表
  traverse() {
    let current = this.head;

    let arr: T[] = [];
    while (current) {
      arr.push(current.value);
      current = current.next;
    }
    const arrStr = arr.join("->");
    console.log(arrStr);

    return arrStr;
  }
  // 根据位置更新节点值
  update(value: T, position: number): boolean {
    if (!this.size) return false;
    const currentNode = this._getNode(position);
    if (!currentNode) return false;
    currentNode.value = value;
    return true;
  }
  // 根据值删除节点
  remove(value: T): T | null {
    const index = this.indexOf(value);
    return this.removeAt(index);
  }
  // 根据值查找节点位置
  indexOf(value: any): number {
    if (!this.size) return -1;
    let current = this.head;
    let index = 0;
    while (index < this.size && current) {
      if (current.value === value) return index;
      current = current.next;
      index++;
    }
    return -1;
  }
  // 判断链表是否为空
  isEmpty(): boolean {
    return this.size === 0;
  }
  // 获取链表长度
  get length(): number {
    return this.size;
  }
}

const linkedList = new LinkedList<string>();

linkedList.append("a");
linkedList.append("b");
linkedList.append("c");
linkedList.removeAt(2);
linkedList.insert("x", 0);
console.log(linkedList.insert("x", 2));

linkedList.traverse();
console.log(linkedList.get(3));
console.log(linkedList.update("y", 1));
linkedList.remove("y");
linkedList.traverse();
console.log(linkedList.indexOf("b"));
